/* ------------------------------------------------------------ */
/*                       file information                       */
/* ------------------------------------------------------------ */

// Filename:  x3mem.c
// Purpose:   Memory management
// License:   MIT/X. (c) OldCoder (Robert Kiraly) 1987-2022.

/* ------------------------------------------------------------ */
/*                         header files                         */
/* ------------------------------------------------------------ */

#include <stdlib.h>
#include <string.h>

#include "inc/x3mem.h"          /* main X3MEM header file       */

/* ------------------------------------------------------------ */
/*                     miscellaneous notes                      */
/* ------------------------------------------------------------ */

/* 1. X3MEM is aka QMALLOC.                                     */

/* 2. Programs  should  not  pass  QMALLOC  storage pointers to */
/* MALLOC functions.                                            */

/* 3. Programs  should  not  pass  MALLOC   storage pointers to */
/* QMALLOC functions.                                           */

/* 4. The following actions may slow programs down:             */
/*                                                              */
/*    (a) frequent calls to "chk_qma()" or "qflush()"           */
/*    (b) frequent calls to the lower-level MALLOC functions    */
/*    (c) frequent requests for blocks larger than "qm_block"   */

/* ------------------------------------------------------------ */
/*                   miscellaneous definitions                  */
/* ------------------------------------------------------------ */

/* convert to alignment units   */

/* If "x" is a size in bytes, "ALIGNSIZ(x)" returns the minimum */
/* number of  "QM_ALIGN"  alignment units  which will hold  the */
/* specified number of bytes.                                   */

#define ALIGNSIZ(x) ((((x3u_long) (x)) + QMASIZE - ONE) / QMASIZE)

/* ------------------------------------------------------------ */

/* QMALLOC block header size    */

                                /* size in bytes                */
#define HDR_BSIZE   (sizeof(QM_HDR))
                                /* size in alignment units      */
#define HDR_ASIZE   ALIGNSIZ(HDR_BSIZE)

/* ------------------------------------------------------------ */

/* null header pointer          */

#define NULLQH      ((QM_HDR *) ZERO)

/* ------------------------------------------------------------ */

/* memory allocation slack      */

/* When "qmalloc()"  allocates a  "qm_free" free block which is */
/* longer than  it needs,  the  unused portion of the  block is */
/* broken off if more than "QM_SLACK" alignment units of usable */
/* storage will be freed up this way.                           */

#define QM_SLACK    (8 / QMASIZE)

/* ------------------------------------------------------------ */

/* return alignment pointer     */

/* "ALIGN_P(x)"  typecasts  the pointer  (x) to  the  alignment */
/* pointer type  "QM_ALIGN *".  The  pointer  value  should  be */
/* suitably aligned before the conversion is done.              */

#define ALIGN_P(x)  ((QM_ALIGN *) (x))

/* ------------------------------------------------------------ */

/* address conversion           */

/* The  "addr(x)" macro is used to work around a  problem  with */
/* the Intel 80X86 system architecture.                         */

#ifdef M_I86                    /* Microsoft C                  */
#define addr(x)     ((x3u_long) ((char far *) (x)))
#else                           /* other systems                */
#define addr(x)     (x)
#endif                          /* endif MSC                    */

/* ------------------------------------------------------------ */

/* return block size            */

/* If  "x" is a  pointer to a  "QM_HDR"  memory  block  header, */
/* "QM_ASIZE(x)"  returns the  size of the block in  "QM_ALIGN" */
/* units as an  unsigned long value.  The  block size  includes */
/* the size of the header itself.                               */

#define QM_ASIZE(x) ((x3u_long) ((x)->qa_size))

/* ------------------------------------------------------------ */

/* return next memory position  */

/* If  "x" is a  pointer to a  "QM_HDR"  memory  block  header, */
/* "NXT_POS(x)"  returns a  "QM_ALIGN"  pointer  to  the  first */
/* "QM_ALIGN"  memory  position  after  the   specified  memory */
/* block.                                                       */

#define NXT_POS(x)  (ALIGN_P(x) + (x)->qa_size)

/* ------------------------------------------------------------ */

/* "qrealloc()" blocking factor */

/* To reduce fragmentation,  "qrealloc()" reallocates memory in */
/* blocks of  "QM_RAFF" bytes.  "QM_RAFF" should be a  power of */
/* two between 2^3 (8) and 2^11 (2048).                         */

#define QM_RAFF     256

/* ------------------------------------------------------------ */
/*                 consistency-check definitions                */
/* ------------------------------------------------------------ */

/* consistency-check codes      */

#define QM_FREE     ((QM_SIZE_T) 0x12345678L)
#define QM_INUSE    ((QM_SIZE_T) 0x87654321L)

/* "QM_HDR" memory block headers normally fall into the follow- */
/* ing four categories:                                         */
/*                                                              */
/*    (a) headers which are in a QLIST "qm_free" list           */
/*    (b) headers which are in the global "sys_free" list       */
/*    (c) headers allocated to higher-level users               */
/*    (d) headers which are in a QLIST "qm_sysmem" list         */

/* If a  "QM_HDR" block header falls into the  first  two cate- */
/* gories here,  "qm_chk" contains a  consistency  check  value */
/* equal  to  "qa_size"  exclusive-or'd with  the  magic number */
/* "QM_FREE".                                                   */

/* If a  "QM_HDR" block header falls into the  second two cate- */
/* gories here,  "qm_chk"  contains a consistency  check  value */
/* equal  to  "qa_size"  exclusive-or'd with the  magic  number */
/* "QM_INUSE".                                                  */

/* ------------------------------------------------------------ */

/* consistency-check macros     */

/* These  six macros each take a single  "QM_HDR" pointer  as a */
/* parameter.                                                   */

/* "qm_relflg(q)"  and  "qm_useflg(q)"  return  the  calculated */
/* values of the  "free" and "used" consistency flags, respect- */
/* ively.                                                       */

/* "qm_setrel(q)" and "qm_setuse(q)" save the correct values of */
/* the "free" and "used" consistency flags, respectively.       */

/* "qm_chkrel(q)" and "qm_chkuse(q)" check the stored values of */
/* the "free" and "used" consistency flags, respectively.       */

/* ------------------------------------------------------------ */

#define qm_relflg(q)    ((q)->qa_size ^ QM_FREE)
#define qm_useflg(q)    ((q)->qa_size ^ QM_INUSE)

#define qm_setrel(q)    ((q)->qm_chk = qm_relflg(q))
#define qm_setuse(q)    ((q)->qm_chk = qm_useflg(q))

#define qm_chkrel(q)    if ((q)->qm_chk != qm_relflg(q)) qm_ce()
#define qm_chkuse(q)    if ((q)->qm_chk != qm_useflg(q)) qm_ce()

/* ------------------------------------------------------------ */
/*                    allocation constraints                    */
/* ------------------------------------------------------------ */

/* default "qm_block" factor    */

/* The constant  "QM_DEFBLK"  specifies the  default  value for */
/* "qm_block".  See the description of "qm_block" in  "x3mem.h" */
/* for additional information.                                  */

/* ------------------------------------------------------------ */

#ifdef M_I86                    /* Microsoft C                  */
#define QM_DEFBLK    512
#endif                          /* endif MSC                    */

#ifdef QMSA                     /* stand-alone version          */
#define QM_DEFBLK    512
#endif                          /* endif "QMSA"                 */

#ifdef VMS                      /* VMS host                     */
#define QM_DEFBLK   8184
#endif                          /* endif VMS                    */

#ifndef QM_DEFBLK               /* set   default value?         */
#define QM_DEFBLK   2036        /* yes                          */
#endif                          /* endif default value          */

/* ------------------------------------------------------------ */

/* If "x" is the "qm_block" value for a given QLIST, "q_more()" */
/* will clip its "n_a" parameter to a minimum of "QM_GETMIN(x)" */
/* alignment units when extending the QLIST.                    */

/* "QM_GETMIN(x)" is chosen so that  "q_more()" will  request a */
/* minimum of  at least "x" bytes when calling "malloc()".  (If */
/* "x" is a multiple of QMASIZE, "q_more()" will request a min- */
/* imum of exactly "x" bytes.)                                  */

/* ------------------------------------------------------------ */

#define QM_GETMIN(x)    (ALIGNSIZ(x) - HDR_ASIZE)

/* ------------------------------------------------------------ */
/*                       public variables                       */
/* ------------------------------------------------------------ */

#ifdef QMSA                     /* stand-alone version          */
char *mempool;                  /* pointer to/into storage pool */
long poolsize;                  /* storage pool size in bytes   */
#endif                          /* endif "QMSA"                 */

/* ------------------------------------------------------------ */
/*                   module-private variables                   */
/* ------------------------------------------------------------ */

MODPRIV char *qm_ce_msg;        /* used by "qm_ce()"            */
                                /* freed system memory blocks   */
MODPRIV QM_HDR *sys_free = NULLQH;

MODPRIV QLIST QM_SQL [ONE];     /* used by "sq..." functions    */

/* ------------------------------------------------------------ */
/*                          functions                           */
/* ------------------------------------------------------------ */

/* Function:    V_OBJ *qm_sbrk(ux)                              */
/* Summary:     Lowest-level "stand-alone" allocation routine.  */

/* ------------------------------------------------------------ */

/* x3u_int ux;      - Number of bytes to allocate (0+).         */

/* ------------------------------------------------------------ */

/* "qm_sbrk()" is the  lowest-level  allocation routine used by */
/* the "stand-alone" version of the QMALLOC package.            */

/* "qm_sbrk()" allocates a  block of the specified size and re- */
/* turns the  associated block pointer.  If the block cannot be */
/* allocated, "qm_sbrk()" returns a null pointer.               */

/* ------------------------------------------------------------ */

#ifdef QMSA                     /* stand-alone version          */
MODPRIV V_OBJ *qm_sbrk (ux)
x3u_int ux;                     /* # of bytes to allocate (0+)  */
{
    long lx;                    /* "signed long" byte count     */
    int n;                      /* "signed int"  byte count     */
    V_OBJ *result;              /* result pointer               */

/* ------------------------------------------------------------ */

    n  = (int) ux;              /* "signed int"  byte count     */
                                /* safety measure               */
    if (n < ZERO) return (NULLVP);
    lx = (long) n;              /* "signed long" byte count     */

    if (mempool == NULLCP)
    {
        x_panic ("Need to initialize mempool and poolsize");
    }

    if (lx > poolsize)          /* sufficient room?             */
    {                           /* no                           */
        return (NULLVP);        /* return a null pointer        */
    }

    result = mempool;           /* point to new block           */
    poolsize -= lx;             /* reduce recorded pool size    */
    mempool  += n;              /* move pointer past new block  */
    return (result);            /* return block pointer         */
}
#endif                          /* endif "QMSA"                 */

/* ------------------------------------------------------------ */

/* Function:    V_FUNC qm_ce(NO_PARAM)                          */
/* Summary:     Handles inconsistent-allocation errors.         */

/* ------------------------------------------------------------ */

/* Various functions  call  "qm_ce()" if it  appears  that  bad */
/* pointers are being  used or  memory is corrupted.  "qm_ce()" */
/* prints an error message and terminates the program.          */

/* "qm_ce()"  produces the message  "inconsistent memory chain" */
/* by default.  The global character pointer "qm_ce_msg" may be */
/* used to specify a secondary message string.  If this pointer */
/* is non-null when "qm_ce()" is called, "qm_ce()" will add the */
/* specified message string to the base message.                */

/* ------------------------------------------------------------ */

MODPRIV V_FUNC qm_ce(NO_PARAM)
{
                                /* base message                 */
    char *msg = "inconsistent memory chain";

    if (qm_ce_msg != NULLCP)    /* add secondary message?       */
    {                           /* yes                          */
        x_panic ("%s: %s",msg,qm_ce_msg);
    }
    else
    {                           /* no                           */
        x_panic (msg);
    }
}

/* ------------------------------------------------------------ */

/* Function:    V_FUNC chk_qm0(cp)                              */
/* Summary:     Checks a dynamic-memory pointer.                */

/* ------------------------------------------------------------ */

/* V_OBJ *cp;       - Dynamic-memory storage pointer previously */
/*                    returned  by  "qmalloc()"  or  a  related */
/*                    function.                                 */

/* ------------------------------------------------------------ */

/* "chk_qm0(cp)"  checks the  "V_OBJ *" pointer  "cp" and term- */
/* inates the  caller with an  error message  if  "cp" is not a */
/* valid "qmalloc()" storage pointer.                           */

/* Note:  A  valid  storage  pointer  becomes  invalid  if  the */
/* associated storage is freed.                                 */

/* "chk_qm0()"  is the  non-macro version of  "chk_qmp()".  See */
/* the description of "chk_qmp()" for additional information.   */

/* ------------------------------------------------------------ */

MODPUB V_FUNC chk_qm0(cp)
V_OBJ *cp;                      /* dynamic-memory pointer       */
{
    REG_VAR QM_HDR *mcb;        /* memory block pointer         */

/* ------------------------------------------------------------ */

    if (cp == NULLVP) qm_ce();  /* check for null pointer       */

                                /* point to the header block    */
    mcb = ((QM_HDR *) cp) - ONE;
    qm_chkuse(mcb);             /* check    the header block    */
}

/* ------------------------------------------------------------ */

/* Function:    V_FUNC chk_qma (qp)                             */
/* Summary:     Checks an entire QLIST.                         */

/* ------------------------------------------------------------ */

/* QLIST *qp;       - QLIST to check.                           */

/* ------------------------------------------------------------ */

/* "chk_qma()"  performs some  consistency checks on the  QLIST */
/* specified by "qp".                                           */

/* ------------------------------------------------------------ */

MODPUB V_FUNC chk_qma (qp)
QLIST *qp;                      /* QLIST to check               */
{
    REG_VAR QM_HDR *mcb;        /* memory block pointer         */

/* ------------------------------------------------------------ */

                                /* check for null pointer       */
    if (qp == NULL_QLS) qm_ce();

/* ------------------------------------------------------------ */

/* The following  block of code checks the free list associated */
/* with the QLIST.                                              */

    for (mcb = qp->qm_free; mcb != NULLQH; mcb = mcb->nxt_free)
    {
        qm_chkrel(mcb);         /* consistency check            */
    }

/* ------------------------------------------------------------ */

/* The following  block of code checks the  system-memory  list */
/* associated with the QLIST.                                   */

    for (mcb = qp->qm_sysmem; mcb != NULLQH; mcb = mcb->nxt_free)
    {
        qm_chkuse(mcb);         /* consistency check            */
    }
}

/* ------------------------------------------------------------ */

/* Function:    long sys_mem()                                  */
/* Summary:     Estimates amount of system memory available.    */

/* ------------------------------------------------------------ */

/* "sys_mem()" estimates the  amount of free (unallocated) sys- */
/* tem memory available and returns the result (in bytes).  The */
/* value returned is conservative (low).                        */

/* ------------------------------------------------------------ */

/* Technical notes:                                             */

/* 1. The  result  does  not include  unused  storage  space in */
/* QLISTs.                                                      */

/* 2. If the host O/S is  MS-DOS, "sys_mem()" assumes  that the */
/* calling program  was  compiled  using  Microsoft C's "large" */
/* memory model.                                                */

/* 3. "WSP_SIZE" should  fall into the range of 5,000 to 50,000 */
/* bytes.                                                       */

/* 4. "WSP_SLOTS" should not exceed 250 under MS-DOS.           */

/* 5. "sys_mem()"  is  accurate  up  to  "WSP_SIZE * WSP_SLOTS" */
/* bytes.                                                       */

/* ------------------------------------------------------------ */

#define WSP_SLOTS     250       /* # of segments to try for     */
#define WSP_SIZE     5120       /* size of each segment         */

/* ------------------------------------------------------------ */

#ifdef QMSA                     /* stand-alone version          */
MODPUB long sys_mem()
{
    return (poolsize);
}
#endif                          /* endif "QMSA"                 */

/* ------------------------------------------------------------ */

#ifndef QMSA                    /* "malloc"-based version       */
MODPUB long sys_mem()
{
    REG_VAR char *cp;           /* single allocation pointer    */
    REG_VAR int i;              /* scratch                      */
    REG_VAR int n_seg;          /* # of segments allocated      */

    char *wsp_ptr [WSP_SLOTS];  /* list of allocation pointers  */

/* ------------------------------------------------------------ */

                                /* try to allocate memory       */
    for (n_seg = ZERO; n_seg < WSP_SLOTS; n_seg++)
    {
        cp = (char *) malloc ((x3u_int) WSP_SIZE);
        if (cp == NULLCP) break;
        wsp_ptr [n_seg] = cp;
    }
                                /* free the allocated memory    */
    for (i = ZERO; i < n_seg; i++)
    {
        free (wsp_ptr [i]);     /* free the current block       */
    }
                                /* return the result            */
    return (((long) n_seg) * (long) WSP_SIZE);
}
#endif                          /* endif not "QMSA"             */

/* ------------------------------------------------------------ */

/* Function:    V_FUNC qfree(cp)                                */
/* Summary:     Frees memory allocated by "qmalloc()".          */

/* ------------------------------------------------------------ */

/* V_OBJ *cp;        - Pointer returned by "qmalloc()" or a re- */
/*                     lated function.                          */

/* ------------------------------------------------------------ */

/* "qfree(cp)"  returns the dynamic memory associated with "cp" */
/* to the QLIST from which it was obtained.                     */

/* "qfree()"  may  be  used  to  free memory  allocated by  the */
/* following functions:                                         */
/*                                                              */
/*      qcalloc()   qmalloc()   qrealloc()                      */

/* "qfree()" should not be used to free memory allocated by the */
/* standard MALLOC functions (calloc, malloc, etc.).            */

/* ------------------------------------------------------------ */

MODPUB V_FUNC qfree (cp)
V_OBJ *cp;                      /* previously-allocated pointer */
{
    REG_VAR QM_HDR *cur_mcb;    /* memory block being freed     */
    REG_VAR x3u_long lx;        /* scratch                      */
    int m_flag;                 /* O.K.-to-merge flag           */
    QM_SIZE_T m_size;           /* merged block size            */
    QM_HDR *nxt_mcb;            /* next block in free list      */
    QM_HDR *prev;               /* preceding block in free list */
    QLIST  *qp;                 /* QLIST to use                 */

/* ------------------------------------------------------------ */

/* initial setup                */

    if (cp == NULLVP) qm_ce();  /* null pointer?                */
                                /* point to the QM_HDR block    */
    cur_mcb = ((QM_HDR *) cp) - ONE;
    qm_chkuse(cur_mcb);         /* consistency check            */
    qm_setrel(cur_mcb);         /* mark block as released       */
    qp = cur_mcb->qm_owner;     /* get the QLIST to use         */
    cur_mcb->nxt_free = NULLQH; /* clear the next-free pointer  */

/* ------------------------------------------------------------ */

/* handle the simplest case     */

    if (qp->qm_free == NULLQH)  /* is QLIST's freelist empty?   */
    {                           /* yes                          */
        qp->qm_free = cur_mcb;  /* stick the freed block in     */
        return;                 /* done - exit                  */
    }

/* ------------------------------------------------------------ */

/* find position in free-list   */

/* When the  following loop is completed,  "prev" points to the */
/* header which should precede "cur_mcb" in the free-list,  and */
/* "nxt_mcb" points to the header which should follow "cur_mcb" */
/* in the list.                                                 */

/* "prev" will be  null  (NULLQH) if  "cur_mcb"  belongs at the */
/* beginning of  the list,  and "nxt_mcb" will be null (NULLQH) */
/* if "cur_mcb" belongs at  the end of the list.  Since we have */
/* already  verified  that  the  list is  nonempty,  "prev" and */
/* "nxt_mcb" cannot both be null.                               */

    prev    = NULLQH;
    nxt_mcb = qp->qm_free;

    while ((nxt_mcb != NULLQH) && (addr(nxt_mcb) < addr(cur_mcb)))
    {
        qm_chkrel(nxt_mcb);     /* consistency check            */
        prev = nxt_mcb;
        nxt_mcb = nxt_mcb->nxt_free;
    }

/* ------------------------------------------------------------ */

/* another consistency check    */

/* Does the preceding  free memory block overlap  the beginning */
/* of the block being freed now?                                */

    if (prev != NULLQH)
    {
        if ((addr(prev) >= addr(cur_mcb)) ||
            (addr(NXT_POS(prev)) > addr(ALIGN_P(cur_mcb))))
        {                       /* yes - consistency error      */
            x_panic ("qfree: overlap -1");
        }
    }

/* ------------------------------------------------------------ */

/* another consistency check    */

/* Does the end of the block being freed now overlap the begin- */
/* ning of the next free block?                                 */

    if (nxt_mcb != NULLQH)
    {
        if ((addr(cur_mcb) >= addr(nxt_mcb)) ||
            (addr(NXT_POS(cur_mcb)) > addr(ALIGN_P(nxt_mcb))))
        {                       /* yes - consistency error      */
            x_panic ("qfree: overlap +1");
        }
    }

/* ------------------------------------------------------------ */

/* Can we merge the block  being freed with the  preceding free */
/* block?                                                       */

    m_flag = FALSE;

    if ((prev != NULLQH) &&
        (NXT_POS(prev) == ALIGN_P(cur_mcb)))
    {                           /* the blocks are adjoining     */
                                /* get the merged block size    */
        lx = QM_ASIZE(prev) + QM_ASIZE(cur_mcb);
                                /* value as it will be stored   */
        m_size = (QM_SIZE_T) lx;
                                /* will the size fit?           */
        if (lx == (x3u_long) m_size) m_flag = TRUE;
    }

    if (m_flag)                 /* can the blocks be merged?    */
    {                           /* yes                          */
        prev->qa_size = m_size; /* set the total size           */
        cur_mcb = prev;         /* point to the resulting block */
        qm_setrel(cur_mcb);     /* set the consistency flag     */
    }
    else
    {                           /* no - put it in the free list */
        if (nxt_mcb == qp->qm_free)
        {                       /* head of free list            */
            if (prev != NULLQH) x_panic ("qfree: prev");
            qp->qm_free = cur_mcb;
        }
        else
        {                       /* inside the free list         */
            if (prev == NULLQH) x_panic ("qfree: prev");
            prev->nxt_free = cur_mcb;
        }
                                /* point to the next block      */
        cur_mcb->nxt_free = nxt_mcb;
    }

/* ------------------------------------------------------------ */

/* Can we merge it with the next block?                         */

    m_flag = FALSE;

    if ((nxt_mcb != NULLQH) &&
        (NXT_POS(cur_mcb) == ALIGN_P(nxt_mcb)))
    {                           /* the blocks are adjoining     */
                                /* get the merged block size    */
        lx = QM_ASIZE(cur_mcb) + QM_ASIZE(nxt_mcb);
                                /* value as it will be stored   */
        m_size = (QM_SIZE_T) lx;
                                /* will the size fit?           */
        if (lx == (x3u_long) m_size) m_flag = TRUE;
    }

    if (m_flag)
    {                           /* yes - do it                  */
                                /* set the total size           */
        cur_mcb->qa_size  = m_size;
        qm_setrel(cur_mcb);     /* set the consistency flag     */
                                /* point to the next block      */
        cur_mcb->nxt_free = nxt_mcb->nxt_free;
    }
}

/* ------------------------------------------------------------ */

/* Function:    V_FUNC q_more(qp,n_a)                           */
/* Summary:     Support function for "qmalloc()".               */

/* ------------------------------------------------------------ */

/* QLIST *qp;       - QLIST to use.                             */
/* x3u_long n_a;    - Memory needed, in units of QMASIZE.       */

/* ------------------------------------------------------------ */

/* "q_more(qp,n_a)" gets the requested amount of dynamic memory */
/* from the freed  system-memory list  (sys_free)  or  from the */
/* operating system and adds it to the specified QLIST.         */

/* "n_a"  includes the size of the  free-list  (qm_free) memory */
/* block header, but not the size of the system ("qm_sysmem" or */
/* "sys_free") memory block header.                             */

/* ------------------------------------------------------------ */

#ifdef QMSA                     /* stand-alone    version       */
MODPRIV int q_more (qp,n_a)
#else                           /* "malloc"-based version       */
MODPRIV V_FUNC q_more (qp,n_a)
#endif                          /* endif "QMSA"                 */

QLIST *qp;                      /* QLIST to use                 */
x3u_long n_a;                   /* # of alloc. units required   */
{
    x3u_long lx;                /* scratch                      */
    QM_HDR *mcb;                /* memory block header pointer  */
    QM_HDR *prev;               /* pointer to preceding block   */
    QM_SIZE_T ux;               /* scratch                      */

/* ------------------------------------------------------------ */

/* adjust request as necessary  */

    lx = (x3u_long) qp->qm_block;
    if (lx == ZERO) lx = QM_DEFBLK;
    lx = QM_GETMIN(lx);
    if (n_a < lx) n_a = lx;

/* ------------------------------------------------------------ */

/* check the general free pool  */

    for (prev = NULLQH, mcb = sys_free;
         mcb != NULLQH;
         prev = mcb, mcb = mcb->nxt_free)
    {                           /* try the next system block    */
        qm_chkrel(mcb);         /* consistency check            */

        if ((QM_ASIZE(mcb) - HDR_ASIZE) >= n_a)
        {                       /* found a block large enough   */
            if (prev == NULLQH) /* at the start of the list     */
            {                   /* delete it  from the list     */
                sys_free = mcb->nxt_free;
            }
            else                /* it's inside the list         */
            {                   /* delete it from the list      */
                prev->nxt_free = mcb->nxt_free;
            }

            break;              /* got it                       */
        }
    }

/* ------------------------------------------------------------ */

/* use the system if necessary  */

    if (mcb == NULLQH)          /* have we got it yet?          */
    {                           /* no - must "malloc()" it      */
        lx = QMASIZE * (HDR_ASIZE + n_a);
        ux = (QM_SIZE_T) lx;

        if (lx != (x3u_long) ux)
        {
#ifdef QMSA                     /* stand-alone    version       */
            return (FALSE);
#else                           /* "malloc"-based version       */
            x_panic ("qmalloc: request too large");
#endif                          /* endif "QMSA"                 */
        }

#ifdef QMSA                     /* stand-alone    version       */
        mcb = (QM_HDR *) qm_sbrk (ux);
#else                           /* "malloc"-based version       */
        mcb = (QM_HDR *) malloc (ux);
#endif                          /* endif "QMSA"                 */
    }

/* ------------------------------------------------------------ */

/* check the results            */

    if (mcb == NULLQH)          /* did we get it?               */
    {                           /* no - error                   */
#ifdef QMSA                     /* stand-alone    version       */
        return (FALSE);
#else                           /* "malloc"-based version       */
        x_error ("insufficient memory");
#endif                          /* endif "QMSA"                 */
    }

/* ------------------------------------------------------------ */

/* build a system memory header */

                                /* size including header itself */
    mcb->qa_size  = n_a + HDR_ASIZE;
    qm_setuse(mcb);             /* set the consistency flag     */

/* ------------------------------------------------------------ */

/* add to system-memory list    */

    mcb->nxt_free = qp->qm_sysmem;
    qp->qm_sysmem = mcb;

/* ------------------------------------------------------------ */

/* build an allocation header   */

    mcb++;                      /* point to new header          */
    mcb->qm_owner = qp;         /* "QLIST" to put it in         */
    mcb->qa_size  = n_a;        /* size including header itself */
    qm_setuse(mcb);             /* set the consistency flag     */

/* ------------------------------------------------------------ */

/* add to QLIST's free-list     */

    qfree ((V_OBJ *) (mcb + ONE));

#ifdef QMSA                     /* stand-alone version          */
    return (TRUE);
#endif                          /* endif "QMSA"                 */
}

/* ------------------------------------------------------------ */

/* Function:    V_OBJ *qmalloc (qp, nb)                         */
/* Summary:     Allocates memory from a QLIST.                  */

/* ------------------------------------------------------------ */

/* QLIST *qp;       - QLIST to use (or QM_GEN).                 */
/* int nb;          - Number of bytes required (1+).            */

/* ------------------------------------------------------------ */

/* "qmalloc(qp,nb)"  allocates  the  specified number of  bytes */
/* from the specified QLIST and returns a  pointer to the allo- */
/* cated block of storage.                                      */

/* If the  caller does not use  multiple allocation lists,  the */
/* predefined general-purpose list "QM_GEN" may be used.        */

/* "nb" is declared as a signed value, but is interpreted as an */
/* unsigned value.                                              */

/* If  the  QLIST  does not  contain  sufficient  free storage, */
/* "qmalloc()" adds dynamic memory to the QLIST as necessary.   */

/* Memory  allocated   by   "qmalloc()"  may  be   freed  using */
/* "qfree()".                                                   */

/* "qmalloc()"  prints  an  error  message and  terminates  the */
/* caller if sufficient memory cannot be allocated.             */

/* See the header file "x3mem.h" for additional information.    */

/* ------------------------------------------------------------ */

/* Internal note:                                               */

/* The  sizes  referred to in the  following code  are in units */
/* of the alignment size (QMASIZE),  with the exception of "nb" */
/* and "nu".                                                    */

/* ------------------------------------------------------------ */

MODPUB V_OBJ *qmalloc (qp, nb)
QLIST *qp;                      /* QLIST to use                 */
int nb;                         /* number of bytes required     */
{
    REG_VAR QM_HDR *mcb;        /* memory block header pointer  */
    REG_VAR QM_HDR *mcx;        /* pointer to left-over block   */
    x3u_long n_a;               /* # of alignment units needed  */
                                /* "malloc()"-compatible size   */
    QM_SIZE_T nu = (QM_SIZE_T) nb;
    REG_VAR QM_HDR *prev;       /* previous header in freelist  */
    REG_VAR x3u_long x_a;       /* size of the left-over block  */

/* ------------------------------------------------------------ */

/* initial setup                */

                                /* set the default QLIST        */
    if (qp == NULL_QLS) x_panic ("qmalloc: null");
    if (nu == ZERO) nu = ONE;   /* check the size request       */
    n_a = ALIGNSIZ(nu);         /* # of alignment units needed  */

    if (qp->qm_nofree == FALSE) /* is the list freeable?        */
    {                           /* yes                          */
        n_a += HDR_ASIZE;       /* include a block header       */
    }

    prev = mcb = NULLQH;        /* initial (null) block pointer */

/* ------------------------------------------------------------ */

/* Search the  QLIST  freelist for a  block of  memory  that is */
/* large enough.                                                */

    while (mcb == NULLQH)       /* got a memory block yet?      */
    {                           /* no - try to get one          */
        for (prev = NULLQH, mcb = qp->qm_free;
             mcb != NULLQH;
             prev = mcb, mcb = mcb->nxt_free)
        {                       /* advance to the next entry    */
            qm_chkrel(mcb);     /* consistency check            */
            if (QM_ASIZE(mcb) >= n_a) break;
        }

        if (mcb == NULLQH)      /* did we find a block?         */
        {                       /* no                           */
#ifdef QMSA                     /* stand-alone    version       */
                                /* get more memory from system  */
            if (q_more (qp, n_a) == FALSE) return (NULLVP);
#else                           /* "malloc"-based version       */
            q_more (qp, n_a);   /* get more memory from system  */
#endif                          /* endif "QMSA"                 */
        }
    }

/* ------------------------------------------------------------ */

/* break block up if necessary  */

/* "mcb"  now  points to the "QM_HDR" header of a  block in the */
/* freelist that is large enough.  If the block is significant- */
/* ly larger than we need it to be, we break it into two pieces */
/* and leave the left-over portion in the freelist.             */

/* The left-over portion must be  split off from the end of the */
/* block, as opposed to  the  beginning.  This  requirement  is */
/* imposed by "qrealloc()".                                     */

/* We don't adjust the  consistency-check field for the  "used" */
/* block (*mcb) here.  If this is necessary,  it is done before */
/* the block is returned.                                       */

/* ------------------------------------------------------------ */

    if ((QM_ASIZE(mcb) - n_a) > (HDR_ASIZE + QM_SLACK))
    {                           /* break it up                  */
                                /* size of the left-over block  */
        x_a = mcb->qa_size - n_a;
        mcb->qa_size  = n_a;    /* set size of "used" block     */

                                /* point to the left-over block */
        mcx = (QM_HDR *) NXT_POS(mcb);
        mcx->qa_size  = x_a;    /* set its size                 */
                                /* set its next-pointer         */
        mcx->nxt_free = mcb->nxt_free;
        qm_setrel(mcx);         /* set its consistency flag     */
        mcb->nxt_free = mcx;    /* put it back in the freelist  */
    }

/* ------------------------------------------------------------ */

/* remove block from freelist   */

    if (mcb == qp->qm_free)     /* at head of freelist?         */
    {                           /* yes - just advance the head  */
        if (prev != NULLQH) x_panic ("qmalloc: prev");
        qp->qm_free = mcb->nxt_free;
    }
    else
    {                           /* no - adjust preceding entry  */
        if (prev == NULLQH) x_panic ("qmalloc: prev");
        prev->nxt_free = mcb->nxt_free;
    }

/* ------------------------------------------------------------ */

/* wrap it up                   */

    if (qp->qm_nofree == FALSE) /* is the list freeable?        */
    {                           /* yes - create a header        */
        mcb->qm_owner = qp;     /* save the (QLIST) owner       */
        mcb->qa_size  = n_a;    /* block size including header  */
        qm_setuse(mcb);         /* set the consistency flag     */
        mcb++;                  /* point to the user's portion  */
    }

    return ((V_OBJ *) mcb);     /* give it away                 */
}

/* ------------------------------------------------------------ */

/* Function:    V_FUNC qflush (qp)                              */
/* Summary:     Releases an entire QLIST.                       */

/* ------------------------------------------------------------ */

/* QLIST *qp;       - QLIST to free.                            */

/* ------------------------------------------------------------ */

/* Globals (in):                */

/* char qm_retsys;  - "Flush to system" flag.                   */

/* ------------------------------------------------------------ */

/* "qflush(qp)"  frees up all of the  dynamic memory associated */
/* with  the  specified  QLIST.  The  freed  memory may be  re- */
/* allocated to any QLIST using "qmalloc()".                    */

/* "qflush(qp)"  clears the  QLIST header  after  releasing the */
/* memory.  The empty QLIST may be  re-used for new  allocation */
/* calls.  If the "qm_nofree" flag is used, this flag should be */
/* re-initialized.                                              */

/* ------------------------------------------------------------ */

/* Technical note:                                              */

/* If the global flag "qm_retsys" is FALSE, "qmalloc()" retains */
/* primary control  of the  freed memory.  This is the  default */
/* mode of operation.                                           */

/* If the global flag "qm_retsys" is TRUE,  "qflush()"  returns */
/* primary control  of the  freed  memory  to  the  lower-level */
/* memory allocation function "malloc()".                       */

/* ------------------------------------------------------------ */

MODPUB V_FUNC qflush(qp)
QLIST *qp;                      /* QLIST to use                 */
{
    REG_VAR QM_HDR *cur_mcb;    /* current memory block header  */
    QM_HDR *nxt_mcb;            /* next    memory block header  */

/* ------------------------------------------------------------ */

    if (qp == (QLIST *) NULLVP) qm_ce();

/* ------------------------------------------------------------ */

    for (cur_mcb = qp->qm_sysmem;
         cur_mcb != NULLQH;
         cur_mcb = nxt_mcb)
    {
        qm_chkuse(cur_mcb);     /* consistency check            */
                                /* point to the next header     */
        nxt_mcb = cur_mcb->nxt_free;

#ifndef QMSA                    /* "malloc"-based version       */
        if (qm_retsys)          /* return memory to system?     */
        {                       /* yes - use "free()"           */
            V_CAST free ((V_OBJ *) cur_mcb);
        }
        else
#endif                          /* endif not "QMSA"             */
        {                       /* no - put it in a common pool */
            qm_setrel(cur_mcb); /* set the consistency flag     */
                                /* move it to "sys_free" list   */
            cur_mcb->nxt_free = sys_free;
            sys_free = cur_mcb;
        }
    }

    p_clr(qp);                  /* clear the QLIST header       */
}

/* ------------------------------------------------------------ */

/* Function:    V_OBJ *qcalloc (qp, num, sz)                    */
/* Summary:     Allocates memory from a QLIST.                  */

/* ------------------------------------------------------------ */

/* QLIST *qp;       - QLIST to use (or QM_GEN).                 */
/* x3u_int num;     - Number of items required (1+).            */
/* x3u_int sz;      - Size of each item.                        */

/* ------------------------------------------------------------ */

/* "qcalloc(qp,num,sz)"  is roughly equivalent to  "qmalloc(qp, */
/* num*sz)" with the distinction  that  "qcalloc()"  clears the */
/* block of memory allocated before returning it.               */

/* Memory  allocated   by   "qcalloc()"  may  be   freed  using */
/* "qfree()".                                                   */

/* ------------------------------------------------------------ */

MODPUB V_OBJ *qcalloc (qp, num, sz)
QLIST *qp;                      /* QLIST to use                 */
x3u_int num;                    /* No. of items required (1+)   */
x3u_int sz;                     /* Size of each item            */
{
    REG_VAR V_OBJ *result;      /* result pointer               */

/* ------------------------------------------------------------ */

    int nb = num * sz;          /* number of bytes required     */
    result = qmalloc (qp, nb);  /* returns  a block (or exits)  */
    b_clr (result, nb);         /* clear  the block obtained    */
    return (result);            /* return the result pointer    */
}

/* ------------------------------------------------------------ */

/* Function:    V_OBJ *qrealloc (cp, nb)                        */
/* Summary:     Re-allocates dynamic memory.                    */

/* ------------------------------------------------------------ */

/* V_OBJ *qp;       - "qmalloc()" storage to reallocate.        */
/* int nb;          - New block size, in bytes (1+).            */

/* ------------------------------------------------------------ */

/* If "cp" is a pointer previously returned by "qmalloc()" or a */
/* related function, "qrealloc(cp,nb)" changes  the size of the */
/* allocated block to the new value "nb".                       */

/* The block may be moved in the process.  "qrealloc()" returns */
/* a pointer to the  new  block location  (or to the  old block */
/* location, if the block is not moved).                        */

/* "nb" is declared as a signed integer,  but interpreted as an */
/* unsigned integer.                                            */

/* The contents of the block are unchanged up to  the lesser of */
/* the old and new block sizes.                                 */

/* Memory  allocated  by   "qrealloc()"  may  be   freed  using */
/* "qfree()".                                                   */

/* "qrealloc()"  prints an  error message  and  terminates  the */
/* caller if sufficient memory cannot be allocated.             */

/* "qrealloc()"  should not  be  used in  conjunction with  the */
/* standard "malloc()" and "free()" functions.                  */

/* ------------------------------------------------------------ */

MODPUB V_OBJ *qrealloc (cp, nb)
V_OBJ *cp;                      /* storage to reallocate        */
int nb;                         /* user request (in bytes)      */
{
    REG_VAR QM_HDR *cur_mcb;    /* QM_HDR being reallocated     */
    REG_VAR QLIST *qp;          /* QLIST to use                 */
    REG_VAR V_OBJ *result;      /* result pointer               */
    REG_VAR x3u_long u_lx;      /* scratch (must be x3u_long)   */
    REG_VAR x3u_int ux;         /* scratch (must be x3u_int )   */

/* ------------------------------------------------------------ */

    REG_VAR x3u_int u_nb;       /* adjusted size request        */
    REG_VAR x3u_int u_nc;       /* number of bytes to copy      */
    REG_VAR x3u_int u_old;      /* size of old block            */

/* ------------------------------------------------------------ */

/* initial setup                */

    if (cp == NULLVP) qm_ce();  /* null pointer?                */
                                /* point to the QM_HDR block    */
    cur_mcb = ((QM_HDR *) cp) - ONE;
    qm_chkuse(cur_mcb);         /* consistency check            */

    qp = cur_mcb->qm_owner;     /* get the QLIST to use         */
    if (nb == ZERO) nb = ONE;   /* check the size request       */
    u_nb = (x3u_int) nb;        /* interpret "nb" as unsigned   */

/* ------------------------------------------------------------ */

/* get size of old block        */

/* "u_old" holds  the  number of bytes  allocated  for the  old */
/* block, excluding the memory block header.                    */

    u_old = (x3u_int) ((QM_ASIZE(cur_mcb) - HDR_ASIZE) * QMASIZE);

/* ------------------------------------------------------------ */

/* adjust the new block size    */

/* To reduce fragmentation,  "qrealloc()" reallocates memory in */
/* blocks of "QM_RAFF" bytes.                                   */

/* To  accomplish this, the following code rounds  "u_nb" up to */
/* the  nearest  "QM_RAFF"  boundary.  The  adjustment  has  no */
/* effect  if  "u_nb"  is   already   aligned  on  a  "QM_RAFF" */
/* boundary.                                                    */

/* The adjustment is  suppressed if the adjusted value will not */
/* fit into an unsigned integer.                                */

/* ------------------------------------------------------------ */

    u_lx = (x3u_long) u_nb;
    u_lx = (((u_lx - ONE) / QM_RAFF) + ONE) * QM_RAFF;
    ux   = (x3u_int) u_lx;
    if (u_lx == (x3u_long) ux) u_nb = ux;

/* ------------------------------------------------------------ */

/* is reallocation necessary?   */

    if ((u_nb <= u_old) && ((u_old - u_nb) < QM_RAFF))
    {                           /* no                           */
        return (cp);            /* return the existing pointer  */
    }

/* ------------------------------------------------------------ */

/* determine the copy count     */

/* The following code sets  "u_nc" to the number of  data bytes */
/* to be copied.                                                */

    u_nc = (u_nb < u_old) ? u_nb : u_old;

/* ------------------------------------------------------------ */

/* reallocate the block         */

                                /* allocate new storage         */
    result = qmalloc (qp,(int) u_nb);

                                /* copy the data                */
#ifdef QMSA                     /* stand-alone    version       */
    {
        char *p1 = result;
        char *p2 = cp;

        while (u_nc-- > ZERO) *p1++ = *p2++;
    }
#else                           /* "malloc"-based version       */
    V_CAST memcpy (result, cp, u_nc);
#endif                          /* endif "QMSA"                 */

    qfree (cp);                 /* free the old block           */
    return (result);            /* return the result pointer    */
}

/* ------------------------------------------------------------ */
/*              simplified QMALLOC interface layer              */
/* ------------------------------------------------------------ */

/* The  following  interface layer can  be used by  application */
/* programs which do not require multiple QLISTs.               */

/* ------------------------------------------------------------ */

/* Function:    V_OBJ *sqCalloc(i,j)                            */
/* Summary:     Similar to "calloc(i,j)".                       */

/* ------------------------------------------------------------ */

/* x3u_int i,j;     - Product of these  two  integers gives the */
/*                    number of bytes to allocate.              */

/* ------------------------------------------------------------ */

MODPUB V_OBJ *sqCalloc(i,j)
x3u_int i;
x3u_int j;
{
    return ((V_OBJ *) qcalloc (QM_SQL, i, j));
}

/* ------------------------------------------------------------ */

/* Function:    V_FUNC sqChkHeap()                              */
/* Summary:     Checks the entire "sq..." heap.                 */

/* ------------------------------------------------------------ */

/* "sqChkHeap()"  performs  some   consistency  checks  on  the */
/* "sq..." heap.                                                */

/* ------------------------------------------------------------ */

MODPUB V_FUNC sqChkHeap()
{
    chk_qma (QM_SQL);
}

/* ------------------------------------------------------------ */

/* Function:    V_FUNC sqChkPtr (p, s)                          */
/* Summary:     Checks an allocated storage pointer.            */

/* ------------------------------------------------------------ */

/* V_OBJ *p;        - Pointer previously returned by one of the */
/*                    "sq..." memory allocation functions.      */
/* char *s;         - Message string (see below).               */

/* "sqChkPtr()"  performs some consistency checks on the speci- */
/* fied pointer.  If  the pointer is invalid, "sqChkPtr()" pro- */
/* duces an error message and terminates the caller.  The error */
/* message includes the specified message string.               */

/* ------------------------------------------------------------ */

MODPUB V_FUNC sqChkPtr (p, s)
V_OBJ *p;
char *s;
{
    if (p == NULLVP)
    {
        if ((s == NULLCP) || (*s == CH_EOS))
        {
            x_panic ("null pointer");
        }
        else
        {
            x_panic ("null pointer: %s",s);
        }
    }

    if ((s != NULLCP) && (*s != CH_EOS)) qm_ce_msg = s;
    chk_qm0 (p);
    qm_ce_msg = NULLCP;
}

/* ------------------------------------------------------------ */

/* Function:    V_FUNC sqFlush()                                */
/* Summary:     Frees all "sq..." storage.                      */

/* ------------------------------------------------------------ */

/* "sqFlush()" releases all of the storage previously allocated */
/* by "sq..." memory allocation functions.  Memory is dealloca- */
/* ted at the system (or "malloc") level.                       */

/* ------------------------------------------------------------ */

MODPUB V_FUNC sqFlush()
{
    qm_retsys++;
    qflush (QM_SQL);
    qm_retsys--;
}

/* ------------------------------------------------------------ */

/* Function:    V_FUNC sqFree (p)                               */
/* Summary:     Frees one storage block.                        */

/* ------------------------------------------------------------ */

/* V_OBJ *p;        - Pointer previously returned by one of the */
/*                    "sq..." memory allocation functions.      */

/* "sqFree(p)"  deallocates  the  storage associated  with  the */
/* specified pointer.                                           */

/* Storage is  returned to the "sq..." dynamic memory pool.  It */
/* is not  released to the system.  (Use "sqFlush()" to deallo- */
/* cate the "sq..." heap at the system level.)                  */

/* ------------------------------------------------------------ */

MODPUB V_FUNC sqFree (p)
V_OBJ *p;
{
    qfree (p);
}

/* ------------------------------------------------------------ */

/* Function:    V_OBJ *sqMalloc (n)                             */
/* Summary:     Similar to "malloc (n)".                        */

/* ------------------------------------------------------------ */

/* x3u_int n;       - Number of bytes to allocate.              */

/* ------------------------------------------------------------ */

MODPUB V_OBJ *sqMalloc(n)
x3u_int n;
{
    return (qmalloc (QM_SQL, (int) n));
}

/* ------------------------------------------------------------ */

/* Function:    V_OBJ *sqRealloc (p, n)                         */
/* Summary:     Similar to "realloc (p, n)".                    */

/* ------------------------------------------------------------ */

/* V_OBJ *p;        - Pointer previously returned by one of the */
/*                    "sq..." memory allocation functions.      */
/* x3u_int n;       - New block size.                           */

/* ------------------------------------------------------------ */

MODPUB V_OBJ *sqRealloc (p, n)
V_OBJ *p;
x3u_int n;
{
    return (qrealloc (p, (int) n));
}
